"""
Problem 85: https://projecteuler.net/problem=85

在方形的网格上,数数就知道一个3*2的矩形含有18个正方形:

虽然不存在恰好含200,0000个正方形的矩形, 不过请你求出所含正方形个数最接近这个数值的矩形的面积。
"""


from functools import lru_cache


def count(length: int, width: int) -> int:
    '''

    p1_______
    |        |
    |_______p2

    for p1:
        for p2:
            res += 1

    >>> assert count(2,3) == count(3,2) == 18
    '''
    res = 0
    for p1x in range(length+1):
        for p1y in range(width+1):
            for p2x in range(p1x+1, length+1):
                for p2y in range(p1y+1, width+1):
                    # print(f'({p1x},{p1y}),({p2x},{p2y})')
                    res += 1

    return res


@lru_cache(None)
def count_recursion(length: int, width: int) -> int:
    '''
    count(n,m+1) = count(n,m) + n(n+1)(m+1)/2

    >>> assert all([count_recursion(n,m+1) == count(n,m) + n*(n+1)*(m+1)//2 for n in range(1,10) for m in range(1,10)])
    '''
    if width == 1:
        return length*(length+1)//2

    if width > length:
        return count_recursion(width, length)

    return count_recursion(length, width-1) + length*(length+1)*width//2


def solution(limit: int = 2000000) -> int:

    res = limit,(0,0)

    maxl = 1+int((2*limit)**0.5)
    for i in range(1,maxl+1):
        for j in range(1,i+1):
            diff = abs(limit - count_recursion(i, j))
            if diff < res[0]:
                res = diff, (i,j)
    
    print(count_recursion(res[1][0],res[1][1]))
    return res


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 1999998
    # (2, (77, 36))
